Okresowość

Limit pamięci: 32 MB

Bajtazar, król Bitocji, zarządził reformę nazwisk swoich poddanych. Nazwiska mieszkańców Bitocji często zawierają powtarzające się frazy, np. w nazwisku Abiabuabiab dwukrotnie występuje fragment abiab. Bajtazar chce zamienić nazwiska swoich poddanych na ciągi bitów takiej samej długości jak ich oryginalne nazwiska. Chciałby przy tym w jakimś stopniu zachować sposób, w jaki w oryginalnych nazwiskach powtarzają się te same frazy.

W dalszej części zadania, dla prostoty, będziemy utożsamiać wielkie i małe litery w nazwiskach. Dla dowolnego ciągu znaków (liter lub bitów) powiemy, że liczba naturalna () jest okresem , jeżeli dla wszystkich . Przez będziemy oznaczać zbiór wszystkich okresów . Na przykład, , oraz .

Bajtazar zdecydował, że każde nazwisko ma zostać zamienione na ciąg bitów:

• tej samej długości co oryginalne nazwisko,
• o dokładnie takim samym zbiorze okresów co oryginalne nazwisko,
• ma to być najmniejszy (w porządku leksykograficznym¹) ciąg bitów spełniający powyższe warunki.

Bajtazar poprosił Cię o napisanie programu, który pomógłby w tłumaczeniu dotychczasowych nazwisk jego poddanych na nowe. W nagrodę będziesz mógł zachować swoje oryginalne nazwisko!

Wejście

W pierwszym wejściu standardowego wejścia znajduje się jedna liczba całkowita - liczba nazwisk do przetworzenia (). Nazwiska są podane w kolejnych wierszach, po jednym w wierszu. Każde z nazwisk składa się z od do wielkich liter (alfabetu angielskiego).

W testach wartych łącznie 30% punktów każde nazwisko składa się z co najwyżej liter.

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. W kolejnych wierszach powinny znajdować się ciągi zer i jedynek (niezawierające odstępów) odpowiadające kolejnym nazwiskom z wejścia. W przypadku, gdy dla danego nazwiska nie istnieje ciąg bitów zgodny z warunkami zadania, należy dla tego nazwiska wypisać "XXX" (bez cudzysłowów).

Przykład

Dla danych wejściowych:

3
ABIABUABIAB
BABBAB
BABURBAB

poprawną odpowiedzią jest:

01001101001
010010
01000010

¹ Ciąg bitów jest mniejszy w porządku leksykograficznym od ciągu bitów , jeżeli dla pewnego , , mamy oraz dla wszystkich mamy .

Autor zadania: Wojciech Rytter.